HW#4 --- last modified February 06 2019 04:18:10..

Solution set.

Due date: Apr 22

Files to be submitted:
  Hw4.zip

Purpose: To gain experience with first-order reasoning and planning algorithms.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO9 -- Students should be able to explain the advantages and disadvantages of the STRIPS representation for planning.

LO10 -- Students should be able to describe the frame problem.

Specification:

Do the following problems and submit them in Hw4.zip. If you decide to do the bonus, submit its files in Hw4.zip as well.

1. Express each of the following as first order logic formula (1/4 pt each): (a) 0 is a Leaf, (b) 1 is a Leaf, (c) If x is a Leaf then x is a Tree, (d) If x is a Tree and y is a Tree then (x,y) is a Tree, (e) the Size of a Leaf is 1, (f) If x is a Tree and Size of x is z and if y is a Tree and the Size of y is w, then Size of (x,y) is z + w, (g) whenever x = y and Tree(x) then Tree(y), (h) whenever x is a Tree and y is a Tree and x=y then Size(x) = Size(y).
2. Using our Natural Deduction system extended by rules for First-order logic, give a formal proof of the formula `alpha :=` there exists an x that is a Tree and the Size of x is 1+1+1.
3. Let the formulas of problem 1 be our KB and `alpha` be as in problem 2. Skolemize the formulas in `KB` and `neg alpha`, convert the result to CNF, and then clauses. Finally, find a resolution refutation. For at least one place where you needed to do unification carefully show the steps the algorithm from class would use.
4. Modify the block world planning domain to make it suitable for building pyramids. I.e., blocks can now be clear on a left or right side and a block might have a left side on some other block and a right side on another block. There should also be a notion of left and right adjacency. Consider the problem of going from the first figure below to the second one:

              b 
   a b c     a c
   

   In the first figure a and c are not adjacent, but a is adjacent on the left of b and c is adjacent on the right. Express the problem of going from the first figure to the second as a planning problem in your planning domain. Show the steps solving it if one is using the GraphPlan algorithm from class.
5. Give an example of the frame problem that might occur with our airplane cargo problem.

Bonus Problem. This bonus problem is worth half of what you lost on the midterm. Download pddl4j. Express your new block world domain of problem 4 as a domain for pddl4j in a file domain.pddl. Then make a problem.pddl file for the problem of going from the figure on the left below to the one on the right:

           i
          c s
scienc   n c e

Show the transcript of you running pddl4j using graphplan as the planner to find a plan that solves this problem. Submit this in the file transcript.txt. I am not going to go over using this software in class, so you will have to figure it out by yourself. Be aware though that there are many examples of domains and problems provided in the software download.

Point Breakdown